/**
 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。
 如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 */
/**
重复使用--完全背包
dp[i] 长度为i是str是否可以被表示
公式：
1-没拼接wordDict[j]的情况：dp[i-wordDict[j].length]
2-没拼接长度到剩余长度的str正好等于要拼接的单词 s.slice(i-wordDict[j].length,i)

初始化： dp[0]=true 递推基础
遍历：拼接有顺序，--排列数--外层背包 内层物品
 */
/**
 * 容量 w = s.length = 8
 * 
 */
var wordBreak = function(s, wordDict) {
  const dp = Array(s.length+1).fill(false);
  dp[0]=true;
  for(let i=0;i<=s.length;i++){
    for(let j=0; j<wordDict.length;j++){
      //没拼接wordDict[j]的情况：dp[i-wordDict[j].length]
      //没拼接长度到剩余长度的str正好等于要拼接的单词 s.slice(i-wordDict[j].length,i)
      if(dp[i-wordDict[j].length]&&wordDict[j]===s.slice(i-wordDict[j].length,i)){
        dp[i]=true;
        
      }
    }
  }
  return dp[s.length];
};

/**
 * review 12.13✅
 */

const wordDict = ["leet", "code"];
console.log('单词拆分', wordBreak(s, wordDict))